import java.util.Scanner;

/**
 * Description:
 * Date: 2024-07-23
 * Time: 22:28
 */
import java.util.*;
public class Main {

/*
    static long qmi(long x,long n,long c) {
        if(n == 0) return 1;
        if(n == 1) return x;
        long tmp = qmi(x,n/2,c) % c;
        return n % 2 == 0 ? (tmp * tmp) % c : (x * tmp * tmp) % c;
    }
*/
//
    static long qmi(long a,long b,long c) {
        long res = 1;
        while(b != 0) {
            if(b % 2 == 1) {
                res = res * a % c; //b 为奇数的话，先乘个 a 上去
                b--;
            }
            a = a * a % c;
            b /= 2;
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        while(t-- > 0) {
            long a = in.nextLong(),b = in.nextLong(),c = in.nextLong();
            System.out.println(qmi(a,b,c));
        }
    }
}
